package tree.avl;

/**
 * Created by root on 3/7/17.
 */
public class AvlNode<T> {

    T element;
    AvlNode<T> left;
    AvlNode<T> right;
    int height;

    public AvlNode(T element) {
        this(element,null,null);
    }

    public AvlNode(T element, AvlNode<T> left, AvlNode<T> right) {
        this.element = element;
        this.left = left;
        this.right = right;
        this.height = 0;
    }

    public AvlNode<T> insert(T x, AvlNode<T> subRoot){
        if(subRoot==null)
            return new AvlNode<T>(x,null,null);

        int compare = compare(x,subRoot.element);

        if(compare<0){
            subRoot.left = insert(x,subRoot.left);
            if(height(subRoot.left)-height(subRoot.right) == 2){
                if(compare(x,subRoot.left.element)<0)
                    subRoot = rotateWithLeftChild(subRoot);
                else
                    subRoot = doubleWithLeftChild(subRoot);
            }
        }
        else if(compare>0){
            subRoot.right = insert(x,subRoot.right);
            if(height(subRoot.right)-height(subRoot.left) == 2){
                if(compare(x,subRoot.right.element)>0)
                    subRoot = rotateWithRightChild(subRoot);
                else
                    subRoot = doubleWithRightChild(subRoot);
            }
        }else
            ;

        subRoot.height = Math.max(height(subRoot.left),height(subRoot.right)) + 1;
        return subRoot;
    }

    private AvlNode<T> doubleWithRightChild(AvlNode<T> k1) {
        k1.right = rotateWithLeftChild(k1.right);
        return rotateWithRightChild(k1);
    }

    private AvlNode<T> rotateWithRightChild(AvlNode<T> k1) {
        AvlNode<T> k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        k2.height = Math.max(height(k2.left),height(k2.right))+1;
        k1.height = Math.max(height(k1.left),height(k1.right))+1;
        return k2;
    }

    private AvlNode<T> doubleWithLeftChild(AvlNode<T> k3) {
        k3.left = rotateWithRightChild(k3.left);
        return rotateWithLeftChild(k3);
    }

    private AvlNode<T> rotateWithLeftChild(AvlNode<T> k2) {
        AvlNode<T> k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        k2.height = Math.max(height(k2.left),height(k2.right))+1;
        k1.height = Math.max(height(k1.left),height(k1.right))+1;
        return k1;
    }

    private int compare(T x, T element) {
        return ((Comparable)x).compareTo((Comparable)element);
    }



    //-----------getter&setter------------
    public T getElement() {
        return element;
    }

    public void setElement(T element) {
        this.element = element;
    }

    public AvlNode<T> getLeft() {
        return left;
    }

    public void setLeft(AvlNode<T> left) {
        this.left = left;
    }

    public AvlNode<T> getRight() {
        return right;
    }

    public void setRight(AvlNode<T> right) {
        this.right = right;
    }

    public int height(AvlNode<T> t) {
        return t==null ? -1 : t.height;
    }

}
